Recognizing patterns within a set of data is important in many fields, including speech recognition, image processing, seismic data, etc. Some image processors collect image data and then pre-process the data to prepare it to be correlated to reference data. Other systems, like speech recognition, are real time where the input data is compared in real time to reference data to recognize patterns. Once the patterns are “recognized” or matched to a reference, the system may output the reference. For example, a speech recognition system may output equivalent text to the processed speech patterns. Other systems, like biological systems, may use similar techniques to determine sequences in molecular strings like DNA.
In some systems, there is a need to find patterns that are imbedded in a continuous data stream. In non-aligned data streams, there are some situations where patterns may be missed if only a single byte-by-byte comparison is implemented. The situation where patterns may be missed occurs when there is a repeated or nested repeating patterns in the input stream or the pattern to be detected. A reference pattern (RP) containing the sequence that is being searched for is loaded into storage where each element of the sequence has a unique address. An address register is loaded with the address of the first element of the RP that is to be compared with the first element of the input pattern (IP). This address register is called a “pointer.” In the general case, a pointer may be loaded with an address that may be either incremented (increased) or decremented (decreased). The value of the element pointed to by the pointer is retrieved and compared with input elements (IEs) that are clocked or loaded into a comparator.
In pattern recognition, it is often desired to compare elements of an IP to many RPs. For example, it may be desired to compare an IP resulting from scanning a finger print (typically one kilobyte for certain combinations of features defined in finger print technology) to a library of RPs (all scan results on file). To do the job quickly, elements of each RP may be compared in parallel with elements in the IP. Each RP may have repeating substrings (short patterns) which are smaller patterns embedded within the RP. Since a library of RPs may be quite large, the processing required may be considerable. It would be desirable to have a way of reducing the amount of storage necessary to hold the RPs. If the amount of data used to represent the RPs could be reduced, it may also reduce the time necessary to load and unload the RPs. Parallel processing may also be used where each one of the. RPs and the IP are loaded into separate processing units to determine matches.
Other pattern recognition processing in biological systems may require the comparison of an IP to a large number of stored RPs that have substrings that are repeated. Processing in small parallel processing units may be limited by the storage size required for the RPs. Portable, inexpensive processing systems for chemical analysis, biological analysis, etc., may also be limited by the amount of storage needed to quickly process large numbers of RPs.
Pattern detection or recognition is a bottleneck in many applications today and software solutions cannot achieve the necessary performance. It is desirable to have a hardware solution for matching patterns quickly that is expandable. It is also desirable to have a system that allows multiple modes of pattern matching. Some applications require an exact match of a pattern in an input data stream to a desired target pattern. In other cases, it is desirable to determine the longest match, the maximum number of characters matching, or a “fuzzy” match where various character inclusions or exclusions are needed.
Many types of pattern recognition require a very large pattern or the comparison of a large number of different patterns to a single input data stream. Using small pattern processing units (PUs) that are programmable to do selected pattern matching, allows these units to have high speed processing while also allowing them to be cascaded to do many patterns in parallel or to allow each processing unit to hold a partition of a very large pattern. While input data is coupled to the processing units in parallel, there is a need to communicate selected information between adjacent processing units to share the results of a pattern matching process, indicate when the pointer of a particular processing unit needs to be indexed if the processing unit has a partition of a large pattern, etc. Since a parallel pattern detection engine (PPDE) may be an IC with a large number of these autonomous PUs, there may be many groupings of the PUs, some used for large pattern matching and others used in multiple pattern matching. In these cases, it is desirable to be able to program which of the autonomous PUs have cascade communication between them enabled or disabled. Additionally, it would be desirable to use the cascade communication to allow advanced matching capabilities by using fewer PUs to match complex regular expressions. Wiring issues dictate that the cascade communication be simple because of the large number of pattern processing that may be placed on an IC.
There is, therefore, a need for a method and circuitry to provide bi-directional communication and isolation between autonomous processing units that is simple, programmable and allows advanced matching capabilities.